🧑💻 Решение задачи про поиск повторяющихся элементов в массиве
Задача: Дан массив с целыми числами длины n, все элементы которого лежат в диапазоне [1, n]. Каждый элемент появляется в массиве либо единожды, либо дважды. Требуется найти все числа, которые появляются дважды. Алгоритм должен работать за O(n).
Решение 1: Довольно очевидный способ с использованием множеств. Создаём два множества, проходимся в цикле по массиву и проверяем, если элемент уже есть в первом множестве, то добавляем его в результирующее множество. Возвращаем результирующее множество.
Решение 2 (быстрее и использует меньше памяти): Используем тот факт, что все числа массива находятся в диапазоне от 1 до n. Создаём результирующий список и идём в цикле по массиву. Вычисляем на основе каждого элемента index, а затем берём элемент массива по этому индексу. Если элемент по индексу неотрицательный, то заменяем его отрицательным. Если отрицательный, то добавляем изначальный элемент в результирующий список.
🧑💻 Решение задачи про поиск повторяющихся элементов в массиве
Задача: Дан массив с целыми числами длины n, все элементы которого лежат в диапазоне [1, n]. Каждый элемент появляется в массиве либо единожды, либо дважды. Требуется найти все числа, которые появляются дважды. Алгоритм должен работать за O(n).
Решение 1: Довольно очевидный способ с использованием множеств. Создаём два множества, проходимся в цикле по массиву и проверяем, если элемент уже есть в первом множестве, то добавляем его в результирующее множество. Возвращаем результирующее множество.
Решение 2 (быстрее и использует меньше памяти): Используем тот факт, что все числа массива находятся в диапазоне от 1 до n. Создаём результирующий список и идём в цикле по массиву. Вычисляем на основе каждого элемента index, а затем берём элемент массива по этому индексу. Если элемент по индексу неотрицательный, то заменяем его отрицательным. Если отрицательный, то добавляем изначальный элемент в результирующий список.
#junior #middle
BY Библиотека собеса по Data Science | вопросы с собеседований
I have no inside knowledge of a potential stock listing of the popular anti-Whatsapp messaging app, Telegram. But I know this much, judging by most people I talk to, especially crypto investors, if Telegram ever went public, people would gobble it up. I know I would. I’m waiting for it. So is Sergei Sergienko, who claims he owns $800,000 of Telegram’s pre-initial coin offering (ICO) tokens. “If Telegram does a SPAC IPO, there would be demand for this issue. It would probably outstrip the interest we saw during the ICO. Why? Because as of right now Telegram looks like a liberal application that can accept anyone - right after WhatsApp and others have turn on the censorship,” he says.
Mr. Durov launched Telegram in late 2013 with his brother, Nikolai, just months before he was pushed out of VK, the Russian social-media platform he founded. Mr. Durov pitched his new app—funded with the proceeds from the VK sale—less as a business than as a way for people to send messages while avoiding government surveillance and censorship.
Библиотека собеса по Data Science | вопросы с собеседований from ua
